package l.l.w.leetcode._047PermutationsII;

import java.util.*;

/**
 * Created by llw on 2017/11/10.
 */
public class _047PermutationsII {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        List<Integer> one = new LinkedList<Integer>();
        getResult(result,0,nums);
        return result;
    }
    private void getResult(List<List<Integer>> result, int i , int[] nums){
        if(i == nums.length - 1){
            ArrayList<Integer> list = new ArrayList<>(nums.length);
            for(int k = 0 ; k < nums.length; ++k){
                list.add(nums[k]);
            }
            result.add(list);
            return;
        }
        int[] used = new int[nums.length-i];
        int len = 0;
        for(int j = i; j < nums.length; ++j){
            if(hasUsed(used,len,nums[j])) continue;
            exchange(nums,i,j);
            getResult(result,i+1,nums);
            exchange(nums,i,j);
            used[len++] = nums[j];
        }
    }

    private boolean hasUsed(int[] used, int num,int end) {
        for(int i = 0 ; i < num;++i){
            if(used[i] == end) return true;
        }
        return false;
    }

    private void exchange(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = {-1,2,0,-1,1,0,1};
        List<List<Integer>> result = new _047PermutationsII().permuteUnique(a);
        System.out.println(result.size());
        System.out.println(result);
//        Collections.sort(result, new Comparator<List<Integer>>() {
//            @Override
//            public int compare(List<Integer> o1, List<Integer> o2) {
//                for(int i = 0; i < o1.size(); ++i){
//                    if(o1.get(i)>o2.get(i))return 1;
//                    else if(o1.get(i) < o2.get(i)) return -1;
//                    else continue;
//                }
//                return 0;
//            }
//        });
//        for(int i = 0; i < result.size(); ++i){
//            System.out.println(result.get(i));
//        }
    }
}